package com.jxb.seven;

/**
 * 乘积最大子数组
 *
 * @author jiaobo
 * @date Created in 2025/1/5 15:55
 **/
public class MaxProductSubarray_152 {

    /*标准DP实现*/
    public int maxProduct(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int answer = nums[0];

        //定义dp数组
        int[] maxDP = new int[nums.length];
        int[] minDP = new int[nums.length];
        maxDP[0] = nums[0];minDP[0] = nums[0];
        //使用状态转移公式，填充DP数组，并计算最大值
        for (int i = 1;i<nums.length;i++) {
            maxDP[i] = Math.max(nums[i],Math.max(maxDP[i-1]*nums[i],minDP[i-1]*nums[i]));
            minDP[i] = Math.min(nums[i],Math.min(maxDP[i-1]*nums[i],minDP[i-1]*nums[i]));
            answer = Math.max(answer,maxDP[i]);
        }
        return answer;
    }

    /*DP+滚动数组实现*/
    public int maxProduct2(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }
        int answer = nums[0],max = nums[0],min = nums[0];

        for (int i = 1;i<nums.length;i++) {
            int currMax = max*nums[i],currMin = min*nums[i];
            max = Math.max(nums[i],Math.max(currMax,currMin));
            min = Math.min(nums[i],Math.min(currMax,currMin));
            answer = Math.max(answer, max);
        }
        return answer;
    }

}
